package com.captain.leetcode.动态规划;

/**
 * Des:
 *
 * @author XL
 * @Date 2022/1/5 21:35
 */
public class 买卖股票的最佳时机2122 {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        if (len == 0) return 0;
        int[][] dp = new int[len + 1][2];
        //初始化
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        //dp[i][0] 持有股票
        //dp[i][1] 未持有股票
        //遍历顺序
        for (int i = 1; i < prices.length; i++) {
            //dp公式: 1.前一天持有股票或者 前一天没有股票,今天购买股票
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            //dp[i][1] 未持有股票
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
        }
        return dp[len - 1][1];
    }

    public static void main(String[] args) {
        System.out.println(new 买卖股票的最佳时机2122().maxProfit(new int[]{7, 1, 5, 3, 6, 4}));

    }

}
